package 链表.环形链表142;

import utils.ListNode;
import utils.Utils;

public class Solution {

    public static ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next.next;
            }else{
                return null;
            }

            if(slow == fast){
                ListNode finNode = head;
                while(slow != finNode){
                    slow = slow.next;
                    finNode = finNode.next;
                }
                return finNode;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        // head = [3,2,0,-4], pos = 1
        ListNode head = new ListNode(-1);
        ListNode h1 = new ListNode(3);
        ListNode h2 = new ListNode(2);
        ListNode h3 = new ListNode(0);
        ListNode h4 = new ListNode(-4);

        head.next = h1;
        h1.next = h2;
        h2.next = h3;
        h3.next = h4;
        h4.next = h2;

        Utils.printInt(detectCycle(head).val);

    }
}